package leetcode.editor.cn;

import java.util.*;

/**
 * Copyright (C) 2023 思创数码科技股份有限公司
 * <p/>
 * 版权所有
 * <p/>
 * 类名　　  : P2454
 * 功能概要  :
 *
 * @author yang wk
 * @date 2024/9/14 16:32
 */
public class P2454 {
    public static void main(String[] args) {
        new P2454().secondGreaterElement(new int[]{2, 4, 0, 9, 6});
    }
    class Solution {
        public int[] secondGreaterElement(int[] nums) {
            int[] res = new int[nums.length];
            Arrays.fill(res, -1);
            Deque<Integer> stack = new ArrayDeque<Integer>();
            PriorityQueue<int[]> pq = new PriorityQueue<int[]>(Comparator.comparingInt(a -> a[0]));
            for (int i = 0; i < nums.length; ++i) {
                while (!pq.isEmpty() && pq.peek()[0] < nums[i]) {
                    res[pq.poll()[1]] = nums[i];
                }
                while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                    pq.offer(new int[]{nums[stack.peek()], stack.peek()});
                    stack.pop();
                }
                stack.push(i);
            }
            return res;
        }
    }

    public int[] secondGreaterElement(int[] nums) {
        int length = nums.length;
        int[] result = new int[length];
        for (int i = 0; i < length; i++) {
            int ele = nums[i];
            int index = -1;
            out:
            for (int j = i + 1; j < length; j++) {
                int greaterEle1 = nums[j];
                if (greaterEle1 > ele) {
                    for (int k = j + 1; k < length; k++) {
                        int greaterEle2 = nums[k];
                        if (greaterEle2 > ele) {
                            index = greaterEle2;
                            break out;
                        }
                    }
                }

            }
            result[i] = index;
        }
        return result;
    }
}
